package com.person.leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 32.最长有效括号
 * 2022-05-16 17:08:59
 **/
public class Sequence_0032_LongestValidParentheses {
    public static void main(String[] args) {
        Solution solution = new Sequence_0032_LongestValidParentheses().new Solution();
        solution.longestValidParentheses("(()");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int longestValidParentheses(String s) {
            //'('入栈
            //')'出栈
            //1.遍历
            int res = 0;
//            res = trival(s);
            res = longestValidParentheses1(s);
            return res;
        }

        //妙
        public int longestValidParentheses1(String s) {
            int maxans = 0;
            Deque<Integer> stack = new LinkedList<Integer>();
            stack.push(-1);
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    stack.push(i);
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        stack.push(i);
                    } else {
                        maxans = Math.max(maxans, i - stack.peek());
                    }
                }
            }
            return maxans;
        }

        //超时
        private int trival(String s) {
            int max = 0;
            for (int i = 0; i < s.length(); i++) {
                for (int j = i + 1; j < s.length() + 1; j++) {
                    int len = validLength(s.substring(i, j));
                    max = len > max ? len : max;
                }
            }
            return max;
        }

        private int validLength(String s) {
            int len = 0;
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    stack.add(c);
                } else {
                    if (stack.size() == 0) {
                        return 0;
                    }
                    Character pop = stack.pop();
                    if (pop == '(') {
                        len += 2;
                    } else {
                        return len;
                    }
                }
            }
            if (stack.size() == 0)
                return len;
            return 0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
